In computer systems, single resources are shared between competing multiple agents through arbitration algorithms that ensure that each of the agents has equitable access to the single resource. For example, if four comparable agents required access to a single device or resource, one arbitration algorithm might ensure that each agent had access to the single device, or resource, 25% of the time. A common arbitration scheme uses a round robin. In a round robin arbitration each of the multiple agents is given equal priority in the arbitration and the round robin arbitration algorithm cycles in a fixed order through the multiple agents that are competing for the resource. Typically, the successful agent is chosen through numerically increasing order. In a specific arbitration cycle, the reference number of a selected agent is stored and then, during the next arbitration window, the next highest agent number is selected. For example, if eight agents request access to a single device or resource, this scheme would assign the competitive agents reference numbers 0 through agent 7 respectively. If the requested device or resource had most recently been accessed by agent 0, this value would be stored and in the succeeding cycle, agent 1 would have exclusive use of the device or resource.
While each competing agent has equal priority for the single resource and receives a pro-rata allotment for accessing the resource, such equal distribution of time slots and periods between multiple agents does not readily adapt to competing agents having different bandwidth requirements or speed capabilities. For example, if one agent operates at a speed such that it requires a resource twice as often as a second agent, this technology makes no provision for these greater requirements. Instead, using the round robin arbitration described, both agents would win the arbitration equally often and each would have equal access to the single resource even though one agent requires the resource twice as often as the other agent. This mismatch between the agent""s bandwidth capabilities and its access to the shared resource impairs overall efficiency.
For example, in a computer system there are often many input/output (I/O) devices which have different bandwidth requirements. A system that supports different speeds of peripheral component interface (PCI) buses, may have cards which utilize data at different speeds. While the following description uses a PCI bus, the invention is not limited to any particular type of bus architecture. Some cards on a PCI bus may run at 33 MHZ while other cards run at 66 MHZ. Assuming an identical number of bits of data used by the two cards, the 66 MHZ card will use data twice as fast as the 33 MHZ card. The PCI card that runs at 33 MHZ are designated as 2X PCI bus cards. These cards use 64 bits of data. Conversely, the PCI bus cards that run at 66 MHZ are designated 4X PCI bus cards and also use 64 bits of data. A third speed of bus card is available which doubles the bandwidth of the 4X PCI bus cards and is designated the 8X PCI bus cards. The 8X PCI bus cards runs at double the bandwidth. If a 2X PCI bus card, a 4X PCI bus card, and an 8X PCI bus card were all configured with a standard round robin arbitration, the three speed cards would be given equal priority for the single resource. However, because of the greater data rates, the 4X PCI bus card and the 8X PCI bus cards are not being used efficiently in this round robin arbitration between the cards of various speeds and bandwidth.
Arbitration schemes have attempted to address this mismatch between high speed agents by devoting additional resource access periods to the higher speed agents. For instance, if an 8 cycle access period is divided between two 2X PCI bus cards (2X PCI#1 and 2X PCI#2), and a single 4X PCI card (4X PCI) a standard round robin arbitration scheme would allow each agent to access the resource {fraction (1/3)} of the time. However, prior arbitration schemes have attempted to give the 4X PCI card twice as much access to the resource then either of the two 2X PCI cards. In an 8 cycle access period, access to the resource could be divided as follows: cycle 0-2X PCI#1; cycle 1-2X PCI#2; cycle 2-4X PCI; cycle 3-4X PCI; cycle 4-2X PCI#1; cycle 5-2X PCI#2; cycle 6-4X PCI and cycle 7-4X PCI.
While this division of the resource among competing agents does lessen the problem, other difficulties are encountered. First, during the cycles in which 4X PCI card has exclusive access to the resource, both the 2X PCI#1 and 2X PCI#2 are deprived of access to the resource. Unless both 2X PCI bus cards have stored enough data to continue processing during that time, the overall efficiency of the system is reduced. Secondly, buffers associated with the 2X PCI bus cards may have to be increased to ensure their access to data during the excluded cycles. These problems are only exacerbated when an 8X PCI bus card is included within the system and increasingly the bandwidth mismatch. In addition, the startup time is delayed for the 2X device if the 4X of 8X card is selected first.
A need therefore exists for an efficient arbitration scheme which accommodates multiple speeds of the competing agents and which efficiently distributes access to the resource in accordance with the various speeds of the competing multiple agents. A further need exists for an efficient arbitration scheme that distributes access to the resource among the multiple agents in an efficient manner, allowing each of the competing agents to effectively use the single resource.
These and other objects, features and technical advantages are achieved by a system and method which according to one aspect of the invention, includes a device for arbitrating access to a resource by a plurality of agents includes logic configures to associate requesting ones of the agents with access tokens. The number of the access tokens assigned to each requesting agent is proportional to its bandwidth or speed in comparison with the other requesting agents. A selector is configured to sequence through the access tokens and select respective ones of the requesting agents associated with the access tokens. The logic may dynamically reconfigure token allocation and distribution to only those agents having a pending service request or may skip tokens allocated to agents not having a pending request. The distribution of tokens is preferably uniform over the total bandwidth space of the agents or requesting agents. In one implementation tokens are in the form of binary numbers. Sequencing through the binary numbers may be based on a reversal of the bits of the numbers or selection of winning agents may be based on a reversal of the bits.
According to another aspect of the invention, a method of arbitrating access to a resource by a plurality of agents associates requesting ones of the agents with access tokens. Numbers of access tokens are associated with each of the requesting agents in proportion to that agent""s bandwidth capabilities and/or requirements with respect to the total bandwidth of all agents. The access tokens are sequenced through and respective ones of the requesting agents are selecting in response to selection of one of its tokens. The method may further include dynamically allocating the access tokens to the requesting ones of the agents and/or skipping selection of nonrequesting ones of the agents in response to an arbitration request. The tokens may be binary numbers wherein the selecting step sequences through the token in a reverse bit sequence order. Selection of agents may be based on a reverse bit sequence order of the binary numbers. The tokens associated with a particular agent may be uniformly distributed amongst all of the tokens.
According to another aspect of the invention, a device equitably arbitrates access to a resource by a plurality of agents such as DMA by a plurality of I/O devices, memory access by plural processors, etc. The invention includes methods and structures to equitably distribute access to resources based on the bandwidth of the requesting device relative to the bandwidth of other requesting devices (i.e., the normalized bandwidth (or speed) of the device). An even distribution may be accomplished using a variety of techniques, including bit reversal of an appropriate sequence of binary numbers, use of a hash function, use of a pseudo-random number generator to spread requests evenly over a large number space, etc.
According to one implementation, the invention includes map logic, a clock and a selector. The map logic defines a plurality of consecutive time slots equal in number to a total normalized bandwidth requirement of the agents, each of the agents assigned a number of time slots proportionate to its own bandwidth requirements. A selector is responsive to a clock for sequencing through the time slots and selecting respective requesting ones of the agents assigned to the time slots.
According to a feature of the invention, the clock may be in the form of a counter providing a repeating sequence of values. The sequence may repeat in correspondence to a total number of time slots defined by the map logic.
According to another feature of the invention, the map logic evenly distributes the time slots assigned to respective ones of the agents over a total number of the consecutive time slots.
According to a still further feature of the invention, each of the time slots is identified by a corresponding one of a monotonically increasing sequence of binary numbers and the map logic maps each of the binary numbers to a target binary number formed by reversing a bit order thereof.
According to a still further feature of the invention, each of the agents is assigned a consecutive sequence of binary numbers starting with a integer multiple of its normalized bandwidth. For example, a device operating at a bandwidth four times that of a slowest device may be assigned four time slots corresponding to a forward binary sequence beginning at 0, 4, 8 or 12 (Chex) and including the next three binary numbers. When reversed, the sequence evenly distributes the assignments to this device over the entire space of, in this example, sixteen possible slots. Time slots assigned to devices or processes not requesting service and unassigned time slots may be skipped or excluded.
According to a still further feature of the invention, each of the agents is assigned a consecutive sequence of binary numbers having a minimized distance between the most significant bits thereof weighted from most to least significant. Thus such that a sequences of binary values associated with a particular agent begins on bit transition boundary minimizing transitions of the most significant bit through the next most significant bit of the series.
According to another feature of the invention, each of the agents is associated with a set of binary numbers corresponding to values obtained by reversing a bit order of respective ones of non-overlapping consecutive sequences of binary numbers, each of the sequences spanning a range proportionate to a bandwidth requirement of respective ones of the agents.
According to another feature of the invention, each of the agents is associated with a set of binary numbers included within respective non-overlapping consecutive sequences of binary numbers, each of the sequences spanning a range proportionate to a bandwidth requirement of respective ones of the agents.
According to another aspect of the invention, a method of arbitrating access to a resource by a plurality of agents includes defining a plurality of consecutive time slots, a number of the time slots assigned to respective ones of the agents in proportion to respective bandwidth parameters thereof. The time slots are then periodically sequenced through and respective ones of the agents assigned to the time slots are selected. Preferably, ones of the time slots assigned to respective ones of the agents are evenly distributed among all of the time slots.
According to a feature of the method, each of the time slots is identified by a corresponding one of a monotonically increasing sequence of binary numbers and the map logic maps each of the binary numbers to a target binary number formed by reversing a bit order thereof.
According to another feature of the inventive method, each of the agents is associated with a consecutive sequence of binary numbers having a minimized distance between the most significant bits thereof According to another feature, each of the agents is associated with a set of binary numbers corresponding to values obtained by reversing a bit order of respective ones of non-overlapping consecutive sequences of binary numbers, each of the sequences spanning a range proportionate to a bandwidth requirement of respective ones of the agents. Another feature includes associating each of the agents with a set of binary numbers included within respective non-overlapping consecutive sequences of binary numbers, each of the sequences spanning a range proportionate to a bandwidth requirement of respective ones of the agents.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.